
/*
回溯
连接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/
题目：剑指 Offer 13. 机器人的运动范围





  

   
    
*/
class Solution {
public:
    bool vis[101][101];
    int ret;
    int m,n,k;
    int dx[4] = {0,0,1,-1};
    int dy[4] = {1,-1,0,0};
    int movingCount(int _m, int _n, int _k) {
        m=_m;
        n=_n;
        k=_k;
        dfs(0,0);
        return ret;
    }
    int sum_dig(int x,int y)
    {
        int sum=0;
        while(x)
        {
            sum+=x%10;
            x/=10;
        }
        while(y)
        {
            sum+=y%10;
            y/=10;
        }
        return sum;
    }
    void dfs(int i,int j)
    {
        int sum = sum_dig(i,j);
        if(sum>k)
            return;
        vis[i][j] = true;
        ret++;
        for(int k=0;k<4;k++)
        {
            int x = dx[k]+i;
            int y = dy[k]+j;
            if(x>=0 && x<m && y>=0 && y<n && vis[x][y]==false)
                dfs(x,y);
        }
    }
};